package com.xq.algorithm.binarytree;

import java.util.Stack;

/**
 *
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
 * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/10.
 *         二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），
 *         排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
 *         任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *         任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 *         任意节点的左、右子树也分别为二叉查找树；没有键值相等的节点。
 */

public class ConverBSTDoubleLinkList {


    //递归解法,类似于中序遍历的递归LDR
    TreeNode tail = null;
    TreeNode head = null;
    public TreeNode Convert(TreeNode rootTree){
        if(rootTree == null){
            return null;
        }
        //左子树
        Convert(rootTree.left);

        //中序转换
        if(head == null){
            head = rootTree;
            tail = rootTree;
        }else {
            rootTree.left = tail;
            tail.right = rootTree;
            tail = rootTree;
        }

        //右子树
        Convert(rootTree.right);
        return head;
    }

    /**
     * 使用栈来实现中序遍历
     * @param rootTree
     * @return
     */
    public TreeNode ConvertWithStack(TreeNode rootTree){
        //如果根节点为 null 返回 null 否则当前节点 cur 指向根节点 pRootOfTree
        if(rootTree == null)return null;
        TreeNode cur = rootTree;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (cur != null || !stack.isEmpty()){
            //将左子树上的节点入栈
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }

            //如果已经到了树的最左边，则将栈中的节点出栈。
            cur=stack.pop();
            if(pre == null){
                //刚开始的时候 pre==null 将最左边的 节点赋值给 rootTree。当前节点复值给pre
                rootTree=cur;
                pre=cur;
            }else {
                //当前节点的左指针指向 前一个节点pre
                cur.left = pre;
                //前一个节点的右指针指向 cur 当前节点
                pre.right = cur;
                pre = cur;
            }
            cur = cur.right;
        }

        return rootTree;
    }


    private class TreeNode{
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}
